// 1. 括号-20-()是否有效
// 2. 括号-32-最长有效括号
// 3. 简化路径-71-简化路径
// 4. 解码-394-字符串解码
// 5. 最小栈-155-最小栈
// 6. 单调栈-496-下一个更大元素
// 7. 单调栈-503-下一个更大元素2
// 8. 单调栈-739-每日温度
// 9. 单调栈-42-接雨水
// 10. 单调栈-84-柱状图中最大矩形

// 11. 滑动窗口-209-长度最小的子数组
// 12. 滑动窗口-239-滑动窗口最大值（待理解-困难）
// 14. 滑动窗口-76-最小覆盖子串-hard -----
// 15. 438-找到字母中的所有字母异位词

// 16. 295-数据流中的中位数
// 13. 小顶堆-347-前k个高频元素（待理解-中等）


// 1. 括号是否符合
// 题意：一段字符串，判断这段字符串组成的括号是否有效
// 思路：栈的解决方式，左括号key，有括号为value，判断栈顶value是否等于i，相同则pop
// 注意：自己构造一个各种括号类型的map
var isValidAllBrackets = (s) => {
  const map = { "{": "}", "[": "]", "(": ")" };
  const stack = [];
  for (let i of s) {
    if (map[i]) {
      stack.push(i)
    } else {
      if (map[stack[stack.length - 1]] === i) {
        stack.pop()
      } else {
        return false
      }
    }
  }
  return stack.length === 0;
}
console.log(isValidAllBrackets('(()))'))

// 2. 最长有效括号
// 题意：最长的有效括号子串 "(()" 最长为2 （），连续，返回最大长度
// 思路：左括号进，右括号出，存的是每个字符的索引，当栈还有剩余说明有效且还在连续，max = Math.max(max, i - stack[stack.length - 1])，没有剩余一定要将当前索引push，意味着已经不连续了是新的起始点
// 注意：初始要push -1 ，栈内没有元素要 push 当前
const longestValidParentheses = (s) => {
  let maxLen = 0;
  const stack = [];
  stack.push(-1);
  for (let i = 0; i < s.length; i++) {
    const c = s[i];
    if (c == '(') {       // 左括号的索引，入栈
      stack.push(i);
    } else {              // 遍历到右括号
      stack.pop();        // 栈顶的左括号被匹配，出栈
      if (stack.length) { // 栈未空
        const curMaxLen = i - stack[stack.length - 1]; // 计算有效连续长度
        maxLen = Math.max(maxLen, curMaxLen);          // 挑战最大值
      } else {            // 栈空了，出问题就需要将当前索引入栈，当做起始位置，新长度的起始位置
        stack.push(i);    // 入栈充当参照
      }
    }
  }
  return maxLen;
}
console.log(longestValidParentheses("(()"))
// 括号问题----
// 1. 括号生成
// 2. 括号是否有效（stack）
// 3. 最长的有效括号（stack）

// 3. 简化路径
// 题解：将一段cd路径简化
// 思路：不同情况不同判断，.和’‘continue；.. pop; 其他push
// 注意： 结果拼接要加/ `/${stack.join('/')}`
var simplifyPath = (path) => {
  let arr = path.split('/').filter(res => res !== '');
  let stack = [];
  for (let c of arr) {
    if (c === '.' || c === '') {
      continue
    } else if (c === '..') {
      stack.pop()
    } else {
      stack.push(c)
    }
  }
  return `/${stack.join('/')}`
}
// console.log(simplifyPath("/home/"))
// console.log(simplifyPath("/../"))
// console.log(simplifyPath('/home//foo/'))
console.log(simplifyPath('/a/./b/../../c/'))

// 4. 字符串解码
// 题解：原串是4个a5个b这种，要转换成全字母
// 思路：要存两个栈，一个存数字，一个存字符，还有零时变量去存拼接的字符和字母，当遇到[ 把临时str和num 全部push 然后归0；当遇见] 把 结果str= 栈顶str + 结果str.repeat(栈顶num)；其他情况全部拼接str
// 注意：数字可能多位，要* 10 叠加；拼接结果： 结果str= 栈顶str + 结果str.repeat(栈顶num)； 字母元素要str += char
var decodeString = (s) => {
  let numsStack = []; // 倍数的栈
  let strStack = []; // 待拼接的str 栈
  let num = 0; // 倍数的搬运工作
  let res = ''; // 结果字符
  for (let char of s) {
    if (!isNaN(Number(char))) { // 遇到数字
      num = num * 10 + Number(char) // 为啥要乘 10 , 可能出现12[a]
    } else if (char === '[') { // 为啥还没遇到str就把str push了，因为 num repeat的str i 与 i+1，就可以解释
      strStack.push(res)
      res = '';
      numsStack.push(num)
      num = 0
    } else if (char === ']') {
      let repeatTimes = numsStack.pop()
      res = strStack.pop() + res.repeat(repeatTimes); // 最后res还没push进，所以是上次次的结果repeat 字符串拼在最前面，然后赋值给res让其重复叠加
    } else {
      res += char
    }
  }
  return res
}
console.log(decodeString('3[a]2[bc]'))

// 5. 最小栈
// 题解：这个栈内的最小值 getmin 存的一直都是最小值
// 思路：每次push 要和最小栈，栈顶比较，去最小；每次pop的时候最小栈也要pop
// 注意：每次push 要和最小栈，栈顶比较，去最小；每次pop的时候最小栈也要pop
var minStack = function () {
  this.x_stack = [];
  this.min_stack = [Infinity]; // 【重要：第一次Math.min 对比对象】
}
minStack.prototype.push = function (x) {
  this.x_stack.push(x)
  this.min_stack.push(Math.min(this.min_stack[this.min_stack.length - 1], x)) //  push的一直都是最小值
}
minStack.prototype.pop = function () {
  this.x_stack.pop()
  this.min_stack.pop()
}
minStack.prototype.top = function () {
  return this.x_stack[this.x_stack.length - 1]
}
minStack.prototype.getMin = function () {
  return this.min_stack[this.min_stack.length - 1]
}

// 6. 单调栈-下一个更大元素-单调递增
// 题解：计算nums2 每个索引位置后面的最大一个元素，nums1 存的是num2对应的数字，求得是这些数字在num2中下一个更大的数
// 思路：循环套while当栈内元素存在且比栈顶大的时候, 则设置：栈顶的下一个最大就是item，否则item并不栈内元素的最大值，push栈等待，最后循环nums1 根据map找到对应数字的下一个最大
// 注意：stack可能还有元素，有则说明这些元素没有下一个最大都是-1
var nextElement = (num1, num2) => {
  let map = new Map();  // 存的是每个元素对应最大元素的结果，便于后面映射去找
  let stack = []; // 存的暂时没找到下一个最大的元素

  let res = [];
  num2.forEach(item => {
    // [7,6,5,9] 9 才会大于前面，所以 7的结果是9；6的结果是9；5的结果也是9 所以要while
    while (stack.length && item > stack[stack.length - 1]) {
      map.set(stack.pop(), item) // 当前下一个更大元素就是item，找到下一个更大了就要pop
    }
    stack.push(item)
  })
  stack.forEach(item => map.set(item, -1)) // 没有下一更大的就是-1

  num1.forEach(item => res.push(map.get(item))) // 获取值
  return res
}
console.log(nextElement(nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2, 9])) // 输入：nums1 = [4,1,2], nums2 = [1,3,4,2]. 输出：[-1,3,-1]

// 7. 单调栈-下一个更大元素2- 单调递增
// 题解：相对于上一题。可循环，从头再找, 每个元素的下一个更大元素
// 思路：将nums拼接一个nums，循环乘2  索引为i%数组长度
// 注意：数组的长度与索引的计算方式 1. 存索引
var nextElement2 = (nums) => { // 有重复
  let n = nums.length
  let stack = []; // 存的是索引
  let res = new Array(n).fill(-1)
  for (let i = 0; i < nums.length * 2 - 1; i++) {
    let index = i % n;  // 存的是索引
    while (stack.length && nums[index] > nums[stack[stack.length - 1]]) {
      res[stack[stack.length - 1]] = nums[index]
      stack.pop()
    }
    stack.push(index)
  }
  return res
}
console.log(nextElement2([1, 2, 3, 4, 5]))
console.log(nextElement2([100, 1, 11, 1, 120, 111, 123, 1, -1, -100]))

// 8.每日温度
// 题解：返回下一个更高温度的在几天后
// 思路：标准的单调递增，最高温度就是i-top
// 注意：标准单调递增
var dayliyTemperatures = (temp) => {
  let n = temp.length;
  let stack = [];
  let res = new Array(n).fill(0);

  for (let i = 0; i < n; i++) {
    while (stack.length && temp[i] > temp[stack[stack.length - 1]]) {
      const top = stack.pop();
      res[top] = i - top;
    }
    stack.push(i)
  }
  return res;
}
console.log(dayliyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))

// 9.接雨水
//    0
// 0``0
// 00`0
// 0000
// left top i
// 上面`就是水 求的所有
// 题解：紧密相连的柱状图，求卡缝里装的最大水容量
// 思路：利用一个单调栈叠加，栈里存的是没找到下一个更大值的索引（单调递减），当出现下一个更大值形成凹槽，计算两个高度差的盛水，是一层一层的 宽度i-left-1（left是pop后的下一个高度）；高度是Math.min(height[left], height[i]) - height[top]，两边取其矮与pop出去的元素形成的差值就是凹槽
// 注意：结果是叠加的，pop是最低高度，left和当前是两边的柱子 1. 要注意宽度计算-1，2. 栈空要判断
var trap = (height) => {
  let res = 0;
  let stack = []; // 单调递减 存下标
  const len = height.length;
  for (let i = 0; i < len; i++) {
    while (stack.length && height[i] > height[stack[stack.length - 1]]) {
      const top = stack.pop(); // 取的是上一个最大
      if (!stack.length) break;
      const left = stack[stack.length - 1] // 左侧边柱子，下一个高度
      const curWidth = i - left - 1; // 间隔不包含自己
      const curHeight = Math.min(height[left], height[i]) - height[top]; // -top top为当前盛水高度底 比齐低的已经计算过 一层一层的计算
      res += curHeight * curWidth;
    }
    stack.push(i)
  }
  return res;
}
console.log(trap([0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]));

// 10.柱状图的最大面积
//     0
//  0  0
//  11 0
// 011000
// 左右都有补0
// 能框下的最大矩形
// 题解： 柱子内所能形成的最大矩形
// 思路：与接雨水相反，栈内存的是单调di增，没有找到下一个更小值的，一直单调递增面积就可以递增，宽度依旧是i-left-1,高度是pop元素
// 注意：要给原数组头尾拼接一个0，方便收集结果 1. 要注意宽度计算-1，2. 栈空要判断
var longestRectAreas = (heights) => {
  let stack = [];
  let arr = [0, ...heights, 0];
  let res = 0;
  for (let i = 0; i < arr.length; i++) {
    while (arr[i] < arr[stack[stack.length - 1]]) {
      let top = stack.pop()
      if (!stack.length) break
      let left = stack[stack.length - 1]
      let width = i - left - 1;
      let heigh = arr[top] // 高度就是top
      res = Math.max(res, width * heigh)
    }
    stack.push(i)
  }
  return res
}
// console.log(longestRectAreas([2, 1, 5, 6, 2, 3]))
console.log(longestRectAreas([3, 2, 1, 1]))


// 11. 滑动窗口-长度最小的子数组
// 题解：长度最小的子串，和要大于等于target
// 思路：求每一个位置，移动right，求和，当sum > target, 求r-l，与min的最小值；sum- left所在的元素 l++
// 注意：符合条件  sum -= nums[l++]; 移动左边的方式  1. 长度初始化为length+ 1，后期如果还是大于 length，则表示一直没达到要求为0
var minSubArrayLen = function (target, nums) {
  // 长度计算一次
  const len = nums.length;
  let l = 0;
  let r = 0;
  let sum = 0;
  let res = len + 1; // 子数组最大不会超过自身
  while (r < len) {
    sum += nums[r++];
    // 窗口滑动
    while (sum >= target) {
      // r始终为开区间 [l, r)
      // res = res < r - l ? res : r - l;
      res = Math.min(res, r - l + 1)
      sum -= nums[l++];
    }
  }
  return res > len ? 0 : res;
};

// 12. 滑动窗口-滑动窗口-最大值-双端队列
// 题解：一个数组，给一个窗口宽度，从前往后滑，输出每一个位置的最大值
// 思路：构造一个双端队列，队头的永远是最大的（存的是索引，比较的是元素），第一个while，当前元素大于队列顶pop；第二个while当栈底索引小于i-k则不再窗口内shift； 当i-k+1>0窗口形成开始收集
// 注意：一次循环，两个while 加元素先pop再push，q[0] <= i-k 不在窗口内，收集结果每次push的都是q[0] 1. 存的索引， 2. 比较的对头值
var maxSlidingWindow = (nums, k) => {
  const q = []; // 双端队列存的是索引
  const res = []; // 返回最大值结果
  for (let i = 0; i < nums.length; i++) {
    // 保证队第一个最大
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop() //先移除新加的
    }
    q.push(i)

    // 如果一直是递减，队内元素大于窗口区间，要符合窗口区间
    while (q[0] <= i - k) {  // 
      q.shift() // 先移除老加的
    }

    // 当i为012时 还不符合窗口区间
    if (i - k + 1 >= 0) { ans.push(nums[q[0]]) }
  }
  return res
}

// 13.滑动窗口-找到字母中所有异位词
var findAnagrams = function(s, p) {
  let window = {}
  let need = {}
  let needLength = 0;
  let valid = 0;

  // 初始化目标
  for(let i = 0; i< p.length; i++){
      let c = p[i]
      need[c] = need[c]? need[c]+1: 1;
  }
  needLength = Object.keys(need).length;
  // console.log(need, needLength)

  let left = 0;
  let right = 0;
  let res = []

  while(right < s.length){
      let c = s[right]
      right++;

      // 更新窗口内信息啊, 
      if(need[c]){
          // window[c] = (window[c] || 0) + 1
          window[c] =  window[c]? window[c]+1: 1;
          if(window[c] === need[c]){
              valid++
          }
      }

      // 判断左侧是否要收缩
      while(right - left >= p.length ){
        console.log(left, right, {...window}, valid)
          if(valid === needLength){
              res.push(left)
          }
          let d = s[left]
          left++
          // 移动左后还原窗口
          if(need[d]){
              if(window[d] === need[d]){
                  valid--
              }
              window[d]--
          }
      }
  }

  return res
};
console.log(findAnagrams("cbaebabacd","abc"), ' 滑动')



// 14.滑动窗口-最小覆盖
var minWindow = function(s, t) {
  let need = {}
  let wind = {};

  let valid = 0;
  let left = 0;
  let right = 0;

  // res
  let start = [];
  let len = Infinity;
  for(let i = 0; i< t.length; i++){
      let c = t[i]
      need[c] = (need[c]|| 0) + 1;
  }


  while(right < s.length){
      let c = s[right];
      right++;

      // 更新窗口内信息
      if(need[c]){
          wind[c] = (wind[c] || 0) + 1;
          if(wind[c] === need[c]){
              valid++
          }
      }

      // 判断左窗口收缩
      while(valid === Object.keys(need).length){
          if(right - left < len){ //  这里处理了最大值
              start = left;
              len = right - left;
          }
          // 更新最小覆盖自拆
          let d = s[left]
          left++;
          if(need[d]){
              if(wind[d] === need[d]){
                  valid--
              }
              wind[d]--
          }
      }
  }

  return len === Infinity ? "" : s.substr(start, len) // 注意这里 substr 用法
};


// 最小的k个数 // 数组中第k个最大的数 // 16. 快排-215-找到第k个最大的元素

// 15.前k个高频 - 小顶堆方法没弄清
var topKFrequent = function(nums, k) {
  const map = new Map()
  nums.forEach(n => {
      map.set(n, map.has(n) ? map.get(n)+1 : 1)
  })
  // 首先将字典转成数组，然后对数组中的第二个元素（频度）从小到大排序
  const list = Array.from(map).sort((a, b) => b[1] - a[1])
  // 截取频率前k高的元素
  return list.slice(0, k).map(n => n[0])
};

// 16. 295-数据流中的中位数
var MedianFinder = function() {
  this.store  = []
};
MedianFinder.prototype.addNum = function(num) {
  if(!this.store.length) return this.store.push(num)

  // 升序排列, 插入排序
  let len = this.store.length;
  while(len - 1 >=0 && num < this.store[len - 1]){
      if(len < 0) break
      len--
  }
  this.store.splice(len, 0, num)

};
MedianFinder.prototype.findMedian = function() {
  let len = this.store.length;
  let midIndex = Math.floor(this.store.length / 2)

  console.log(this.store, '====');
  if(len % 2 === 0 ){
      return (this.store[midIndex] + this.store[midIndex -1]) * 0.5
  } else {
      return this.store[midIndex]
  }
};


let a = new MedianFinder()
a.addNum(1)
a.addNum(2)
console.log(a.findMedian())
a.addNum(3)
console.log(a.findMedian())